package com.itheima.leetcode.od.b.greedy;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.LinkedList;

/**
 * (B卷,200分)- 最少面试官数（Java & JS & Python）
 * <p>
 * 题目描述
 * <p>
 * 某公司组织一场公开招聘活动，假设由于人数和场地的限制，每人每次面试的时长不等，并已经安排给定，用(S1,E1)、 (S2,E2)、 (Sj,Ej)…(Si < Ei，均为非负整数)表示每场面试的开始和结束时间。
 * <p>
 * 面试采用一对一的方式，即一名面试官同时只能面试一名应试者，一名面试官完成一次面试后可以立即进行下一场面试，且每个面试官的面试人次不超过 m。
 * <p>
 * 为了支撑招聘活动高效顺利进行，请你计算至少需要多少名面试官。
 * <p>
 * 输入描述
 * <p>
 * 输入的第一行为面试官的最多面试人次 m，第二行为当天总的面试场次 n，
 * <p>
 * 接下来的 n 行为每场面试的起始时间和结束时间，起始时间和结束时间用空格分隔。
 * <p>
 * 其中， 1 <= n, m <= 500
 * <p>
 * 输出描述
 * 输出一个整数，表示至少需要的面试官数量。
 * <p>
 * 用例
 * <p>
 * 输入	2
 * <p>
 * 5
 * <p>
 * 1 2
 * <p>
 * 2 3
 * <p>
 * 3 4
 * <p>
 * 4 5
 * <p>
 * 5 6
 * <p>
 * 输出	3
 * <p>
 * 说明	总共有 5 场面试，且面试时间都不重叠，但每个面试官最多只能面试 2 人次，所以需要 3 名面试官。
 * <p>
 * 输入	3
 * <p>
 * 3
 * <p>
 * 1 2
 * <p>
 * 2 3
 * <p>
 * 3 4
 * <p>
 * 输出	1
 * <p>
 * 说明	总共有3场面试，面试时间不重叠，每个面试官最多能面试3人次，所以只需要一名面试官
 * <p>
 * 输入	3
 * <p>
 * 3
 * <p>
 * 8 35
 * <p>
 * 5 10
 * <p>
 * 1 3
 * <p>
 * 输出	2
 * <p>
 * 说明	总共有3场面试，[5,10]和[8,35]有重叠，所以至少需要2名面试官
 * <p>
 * <p>
 * 题目解析
 * <p>
 * 本题要想面试官人数最少，则需要每个面试官面试尽量多的人。
 * <p>
 * 我们将每个面试官想象成一个桶，每个面试者想象成一个球。
 * <p>
 * 首先，我们需要对面试者的面试时间段，按照结束时间进行升序。
 * <p>
 * 求解最大不相交区间数，需要将区间按结束位置升序：
 * <p>
 * 华为OD机试 - 最多等和不相交连续子序列（Java & JS & Python）_华为机试_伏城之外的博客-CSDN博客
 */
public class MinimumInterviewers {
    public static void main(String[] args) {
        /*Scanner sc = new Scanner(System.in);
        int m = sc.nextInt();
        int n = sc.nextInt();

        int[][] ranges = new int[n][2];
        for (int i = 0; i < n; i++) {
            ranges[i][0] = sc.nextInt();
            ranges[i][1] = sc.nextInt();
        }*/

        int m = 2;
        int n = 5;

        String input = "1 2\n2 3\n3 4\n4 5\n5 6";
        int[][] ranges = Arrays.stream(input.split("\n"))
                .map(s -> Arrays.stream(s.split(" "))
                        .mapToInt(Integer::parseInt)
                        .toArray())
                .toArray(int[][]::new);

        System.out.println(getResult(m, n, ranges));
    }

    /**
     * 贪心算法
     *
     * @param m
     * @param n
     * @param ranges
     * @return
     */
    public static long getResult(int m, int n, int[][] ranges) {
        // 求解最大不相交区间时，需要将所有区间按照右边界升序
        Arrays.sort(ranges, (a, b) -> a[1] - b[1]);

        ArrayList<LinkedList<Integer>> buckets = new ArrayList<>(); // n 场面试最多需要 n 个人
        for (int i = 0; i < n; i++) {
            buckets.add(new LinkedList<>());
        }

        for (int[] range : ranges) {
            int s = range[0];
            int e = range[1];

            for (LinkedList<Integer> bucket : buckets) { // 每个桶都贪心一遍
                // 每个面试官最多面试m次
                if (bucket.size() < m && (bucket.size() == 0 || bucket.getLast() <= s)) {
                    bucket.add(e);
                    break;
                }
            }
        }

        return buckets.stream()
                .filter(bucket -> bucket.size() > 0)
                .count();
    }
}